﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

void Swap(int*a, int*b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void Adjustup(int* arr, int son)
{
	int father = (son - 1) / 2;
	while (son > 0)
	{
		if (arr[father] > arr[son])
		{
			Swap(&arr[father], &arr[son]);
		}
		else
		{
			break;
		}
		son = father;
		father = (son - 1) / 2;
	}
}

void Adjusdown(int* arr, int father, int k)
{
	int son = father * 2 + 1;
	while (son < k)
	{
		if (son + 1 < k && arr[son + 1] < arr[son])
		{
			son++;
		}
		if (arr[father] > arr[son])
		{
			Swap(&arr[father], &arr[son]);

		}
		else
		{
			break;
		}
		father = son;
		son = father * 2 + 1;
	}
	
}



void HeapSort(int* arr, int n)
{
	int i = 0;
	//child = n-1;
	//parent =( n-1-1)*2
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		Adjusdown(arr, i, n);
	}

	//for (i = n-1; i > 0; i--)
	//{
	//	Adjustup(arr, i);
	//}

 	for (i = 0; i < n-1; i++)
	{	 
		Swap(&arr[0], &arr[n - 1-i]);
		Adjusdown(arr, 0, n-1-i);
	}

}

void CreateNDate()
{
	// 造数据
	int n = 10000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (size_t i = 0; i < n; ++i)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

void PrintTopK(int k)
{
	int* arr = (int*)malloc(sizeof(int) * k);
	if (arr == NULL)
	{
		perror("PrintTopk::malloc");
		return;
	}
	FILE* fp = fopen("data.txt", "r");

	for (int i = 0; i < k; i++)
	{
		fscanf(fp, "%d\n", &arr[i]);
	}
	HeapSort(arr, k);
	int tmp = 0;
	while(fscanf(fp,"%d\n",&tmp)!=EOF)
	{
		if (tmp > arr[k - 1])
		{
			arr[k - 1] = tmp;
			HeapSort(arr,k);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", arr[i]);

	}
	free(arr);
	fclose(fp);
}

int main()
{
	//int arr[] = { 6,27,11,3,4,2,1 };
	int k = 0;
	//HeapSort(arr,7);
	printf("请输入K：");
	scanf("%d", &k);
	PrintTopK(k);
	return 0;
}
